package _01_排序;

import com.sun.org.apache.bcel.internal.generic.NEW;

/*
    使用计数排序对其进行加工
    ◼ 基数排序非常适合用于整数排序（尤其是非负整数），因此本课程只演示对非负整数进行基数排序
    ◼ 执行流程：依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）
    稳定的排序,平均时间复杂度:O(d*(n+k)),d是最大值的位数,k是进制；空间复杂度O(n+k) k是进制
 */
public class RadixSort09 extends Sort<Integer>{
    @Override
    protected void sort() {
        //找出最大值
        int max = array[0];
        for(int i=1;i<array.length;++i){
            if(array[i]>max){
                max = array[i];
            }
        }

        int[] newArray = new int[array.length]; //存放排完序的数组
        int[] counts = new int[10]; //范围数组，0~9


        /*
            个位: 593 / 1 % 10 = 3
            十位: 593 / 10 % 10 = 9
            百位: 593 / 100 % 10 = 5
         */
        //要对每一位都进行计数排序，传进去的可能是个位，十位，百位
        for(int divider=1;divider<=max;divider *=10){
            countingSort(divider, newArray,counts);
        }
    }

    private void countingSort(int divider,int[] newArray,int[] counts){
        //初始化
        for(int i=0;i<counts.length;++i){
            counts[i] = 0;
        }

        //最小值是0，所以不用-0,对传进来的每一位都进行%10,计算在counts的位置
        for(int i=0;i<array.length;++i){
            counts[array[i] / divider % 10]++;
        }

        //统计之前数字个数和位置信息
        for(int i=1;i<counts.length;++i){
            counts[i] += counts[i-1];
        }

        //计算出排序后的索引,从右向左
        for(int i=newArray.length-1;i>=0;--i){
            newArray[--counts[array[i] / divider % 10]] = array[i];
        }

        //覆盖
        for(int i=0;i<array.length;++i){
            array[i] = newArray[i];
        }
    }
}
